/* 链式队列定义 */
typedef Vertex QElemSet;
#define NIL -1 /* 顶点不存在时的返回值 */

typedef struct QueueNode *QPosition; /* 指针即结点位置 */
struct QueueNode {
    QElemSet data; /* 存储数据 */
    QPosition next; /* 链接队列中下一个元素的位置 */
};
typedef struct QueueHeadNode *Queue;
struct QueueHeadNode {
    int size; /* 链接队列中当前元素个数 */
    QPosition front; /* 链接队列的队首指针，初始化为NULL */
    QPosition rear; /* 链接队列的队尾指针，初始化为NULL */
};

void InitQueue(Queue queue) {
    /* 初始化一个空的链接队列 */
    queue->size = 0;
    queue->front = NULL;
    queue->rear = NULL;
}

bool IsEmpty(Queue queue) {
    /* 判断队列是否为空 */
    if (queue->size == 0)
        return true;
    else
        return false;
}

void EnQueue(Queue queue, QElemSet x) {
    QPosition new_node;

    new_node = (QPosition)malloc(sizeof(struct QueueNode));
    new_node->data = x;
    new_node->next = NULL;
    if (IsEmpty(queue)) { /* 特殊处理插入空队列的情况 */
        queue->rear = new_node;
        queue->front = new_node;
    } else {
        queue->rear->next = new_node;
        queue->rear = queue->rear->next;
    }
    queue->size++;
}

QElemSet GetFront(Queue queue) {
    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
        return NIL;
    } else {
        return queue->front->data;
    }
}

void DeQueue(Queue queue) {
    QPosition temp;

    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
    } else {
        temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
        queue->size--;
        if (queue->front == NULL) {
            /* 特殊处理删除后变为空的队列 */
            queue->rear = NULL;
        }
    }
}

void DestroyQueue(Queue queue) {
    free(queue);
}
/* 链式队列定义结束 */

bool ExistPath(LGraph graph, Vertex u, Vertex v) {
    Queue queue;
    Vertex w;
    Position p;
    bool *visited, ret;

    /* 初始化辅助工具：访问标识和队列 */
    visited = (bool *)malloc(sizeof(bool) * graph->n_verts);
    for (w = 0; w < graph->n_verts; w++) {
        visited[w] = false;
    }
    queue = (Queue)malloc(sizeof(struct QueueHeadNode));
    InitQueue(queue);
    ret = false; /* 默认返回值为false */
    /* 初始化结束 */
    EnQueue(queue, u); /* 起始顶点入列 */
    visited[u] = true;
    while (IsEmpty(queue) == false) { /* BFS */
        w = GetFront(queue);
        if (w == v) { /* 若访问到v，则说明路径存在 */
            ret = true;
            break;
        }
        DeQueue(queue);
        p = graph->ver_list[w]->adj;
        while (p != NULL) { /* 并将其邻接点入队 */
            if (visited[p->dest] == false) {
                EnQueue(queue, p->dest);
                visited[p->dest] = true;
            }
            p = p->next;
        }
    }
    DestroyQueue(queue);
    free(visited);
    return ret; /* 若完成BFS都没有遇到v，则返回默认的false */
}